#include <iostream>

// 模板类 : 模板化的是成员变量的类型
// 类模板的名字不能单独作为类型出现
// 得跟模板的类型参数一起
// 类模板的定义 必须是 显式调用

// 类模板的声明和定义必须放在一起，不能分开
template <typename T>
class DynamicArray
{
public:
    DynamicArray();                          // 无参构造
    ~DynamicArray();                         // 析构
    DynamicArray(const DynamicArray &array); // 拷贝构造

    // 重载
    DynamicArray &operator=(const DynamicArray &array);

    // 插入
    void InsertTail(const T &element);
    void InsertHead(const T &element);

    // 删除
    void RemoveByIndex(int index); // 按下标删除
    void RemoveByElement(const T element);

    // 显示
    void show();

    // 友元
    // 友元不能共享模板的模板声明，而且不能重名
    template <typename U>
    friend std::ostream &operator<<(std::ostream &os, const DynamicArray<U> &array);

private:
    T *a;
    int size;
    int capacity;
};

// 函数类外定义
// 无参构造
template <typename T>
DynamicArray<T>::DynamicArray()
{
    capacity = 15;
    size = 0;
    a = new T[capacity];
}

// 拷贝
template <typename T>
DynamicArray<T>::DynamicArray(const DynamicArray<T> &array)
{
    capacity = array.capacity;
    size = array.size;
    a = new T[capacity];
    for (int i = 0; i < size; i++)
    {
        a[i] = array.a[i];
    }
}

// 析构
template <typename T>
DynamicArray<T>::~DynamicArray()
{
    delete[] a;
}

// 重载
template <typename T>
DynamicArray<T> &DynamicArray<T>::operator=(const DynamicArray &array) // 赋值运算符重载
{
    capacity = array.capacity;
    size = array.size;
    a = new T[capacity];
    for (int i = 0; i < size; i++)
    {
        a[i] = array.a[i];
    }
    return *this;
}

// 插入
template <typename T>
void DynamicArray<T>::InsertTail(const T &element) // 头插
{
    if (size >= capacity)
    {
        capacity *= 2;
        T *newP = new T[capacity];
        for (int i = 0; i < size; i++)
        {
            newP[i] = a[i];
        }
        delete[] a;
        a = newP;
    }
    a[size++] = element;
}

template <typename T>
void DynamicArray<T>::InsertHead(const T &element) //头插法
{
    {
        if (size >= capacity)
        {
            capacity *= 2;
            T *newP = new T[capacity];
            for (int i = 0; i < size; i++)
            {
                newP[i] = a[i];
            }
            delete[] a;
            a = newP;
        }
        for (int i = size; i > 0; i--)
            a[i] = a[i - 1];
        a[0] = element;
        size++;
    }
}

// 删除
template <typename T>
void DynamicArray<T>::RemoveByIndex(int index) // 按下标删除
{
    if (index < 0 || index >= size)
    {
        std::cout << "input index error!\n";
        return;
    }
    for (int i = index; i < size - 1; i++)
    {
        a[i] = a[i + 1];
    }
    size--;
}

template <typename T>
void DynamicArray<T>::RemoveByElement(const T element) // 按元素删除
{
    for (int i = 0; i < size; i++)
    {
        if (a[i] == element)
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

// 显示
template <typename T>
void DynamicArray<T>::show()
{
    for (int i = 0; i < size; i++)
    {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;
}

template <typename T>
std::ostream &operator<<(std::ostream &os, const DynamicArray<T> &array)
{
    for (int i = 0; i < array.size; i++)
    {
        std::cout << array.a[i] << " ";
    }
    return os;
    std::cout << std::endl;
}
